// @algorithm @lc id=234 lang=cpp 
// @title palindrome-linked-list


#define print(...)
// @test([1,2,2,1])=true
// @test([1,2])=false
class Solution {
public:
    ListNode * Reverse(ListNode * head){
        ListNode *cur = head, *pre = NULL;
        while(cur){
            auto next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    ListNode * Half(ListNode * head){
        auto half = head;
        while(head->next && head->next->next){
            half = half->next;
            head = head->next->next;
        }
        return half;
    }
    bool isPalindrome(ListNode* head) {
        auto half = Half(head);
        auto rev = Reverse(half->next);
        print("head=", head, "\n")
        print("rev=", rev, "\n")
        while(head && rev){
            if(head->val != rev->val)
                return false;
            head = head->next;
            rev = rev->next;
        }
        return true;

    }
};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */